from McTree import *
from McTree import McTree as Tree
import sys

def search(string, pattern):
    """
    Searches for exacts matches of pattern in string, using a suffixtree.
    Returns occurences of these matches. If no matches are found, returns False.
    """
    # Build tree over contents of f.
    tree = Tree(string)

    #print tree
    #print tree.root.edges['W'].edges['a'].edges['r'].edges
    # -= Search for pattern=-
    # Access root and find subtree.
    try:
        n = tree.root.edges[pattern[0]]
    except:
        return False
    i = 0
    j = 0
    #print "Going down", n
    while i < len(pattern):
        if n.start+j == n.stop:
            #print "At the end of edge", n,
            if not n.edges.has_key(pattern[i]):
                return False
            n = n.edges[pattern[i]]
            #print "and choosing", n
            j = 0
        #print "Comparing '%s' vs. '%s' on path %s" %(pattern[i], string[n.start+j],n.getPath())
        if not pattern[i] == string[n.start+j]:
            return False
        i += 1
        j += 1

    #print "Found subtree", n.getPath()

    # Now traverse subtree n
    res = list()
    def traverse(n):
        #print "Visiting edge", getPath(), e.edge
        # For each outgoing edge 'e' from n
        if type(n) == Leaf:
            res.append(n.pos)
        else:
            for e in n.edges.itervalues():
                if type(e) == Leaf:
                    res.append(e.pos+1)
                else:
                    traverse(e)
    #print n.edges
    traverse(n)
    res.sort()
    return res
            


def main(filename, pattern):
    try:
        f = open(filename)
    except IOError, e:
        print e
        return False
    except BaseException, e:
        print "Could not open file %s! Error given:\n%s" %(filename, e)
        return False

    s = f.read()
    #s = s.replace('\n','')
    res = search(s, pattern)
    f.close()
    if res == False:
        print "Oh no... "
    else:
        print ' '.join(map(str, res))    

if __name__ == '__main__':    
    if __file__.endswith('idle.pyw'):
        main('mississippi.txt', 'ss')
    else:
        if len(sys.argv) < 3:
            print "Usage: python %s <input file> <pattern>" %__file__
            print "Outputs occurences of pattern in input file."
        elif len(sys.argv) > 3:
            sys.exit("Wrong call command. See -help")
        else:
            main(sys.argv[1], sys.argv[2])
    
